{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Building Boxes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #math #binary-search"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数学 #二分查找"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minimumBoxes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #放置盒子"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>有一个立方体房间，其长度、宽度和高度都等于 <code>n</code> 个单位。请你在房间里放置 <code>n</code> 个盒子，每个盒子都是一个单位边长的立方体。放置规则如下：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>你可以把盒子放在地板上的任何地方。</li>\n",
    "\t<li>如果盒子 <code>x</code> 需要放置在盒子 <code>y</code> 的顶部，那么盒子 <code>y</code> 竖直的四个侧面都 <strong>必须</strong> 与另一个盒子或墙相邻。</li>\n",
    "</ul>\n",
    "\n",
    "<p>给你一个整数 <code>n</code> ，返回接触地面的盒子的 <strong>最少</strong> 可能数量<em>。</em></p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2021/01/24/3-boxes.png\" style=\"width: 135px; height: 143px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 3\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>上图是 3 个盒子的摆放位置。\n",
    "这些盒子放在房间的一角，对应左侧位置。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2021/01/24/4-boxes.png\" style=\"width: 135px; height: 179px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 4\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>上图是 3 个盒子的摆放位置。\n",
    "这些盒子放在房间的一角，对应左侧位置。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2021/01/24/10-boxes.png\" style=\"width: 271px; height: 257px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 10\n",
    "<strong>输出：</strong>6\n",
    "<strong>解释：</strong>上图是 10 个盒子的摆放位置。\n",
    "这些盒子放在房间的一角，对应后方位置。</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 <= n <= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [building-boxes](https://leetcode.cn/problems/building-boxes/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [building-boxes](https://leetcode.cn/problems/building-boxes/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['3', '4', '10']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumBoxes(self, n: int) -> int:\n",
    "        if n<=2:\n",
    "            return n\n",
    "        for i in range(1, n):\n",
    "            sum1 = i * (i + 1) * (i + 2)  // 6\n",
    "            if sum1 == n:\n",
    "                return i * (i + 1) // 2\n",
    "            if sum1 > n:\n",
    "                i -= 1\n",
    "                break\n",
    "        num = i * (i + 1)*(i + 2) // 6\n",
    "        step = i\n",
    "        for j in range(1, n):\n",
    "            num += j\n",
    "            if num >= n:\n",
    "                return step * (step + 1) //2 +j\n",
    "        assert False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumBoxes(self, n: int) -> int:\n",
    "        ret = 0\n",
    "        level = 1\n",
    "        while n > 0:\n",
    "            for i in range(1, level+1):\n",
    "                n -= i\n",
    "                ret += 1\n",
    "                if n <= 0:\n",
    "                    return ret\n",
    "            level += 1\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumBoxes(self, n: int) -> int:\n",
    "        if n<=2:\n",
    "            return n\n",
    "        for i in range(1, n):\n",
    "            sum1 = i * (i + 1) * (i + 2)  // 6\n",
    "            if sum1 == n:\n",
    "                return i * (i + 1) // 2\n",
    "            if sum1 > n:\n",
    "                i -= 1\n",
    "                break\n",
    "        num = i * (i + 1)*(i + 2) // 6\n",
    "        step = i\n",
    "        for j in range(1, n):\n",
    "            num += j\n",
    "            if num >= n:\n",
    "                return step * (step + 1) //2 +j\n",
    "        assert False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumBoxes(self, n: int) -> int:\n",
    "        for i in range(n):\n",
    "            if i*(i+1)*(i+2)//6 == n:\n",
    "                return i*(i+1)//2\n",
    "            if i*(i+1)*(i+2)//6 > n:\n",
    "                i -= 1\n",
    "                break\n",
    "        remain = n-i*(i+1)*(i+2)//6\n",
    "        botton = i*(i+1)//2\n",
    "        for j in range(i+2):\n",
    "            k = j*(j+1)//2\n",
    "            if remain <= k:\n",
    "                return botton+j"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumBoxes(self, n: int) -> int:\n",
    "        cur = i = j = 1\n",
    "        while n > cur:\n",
    "            n -= cur\n",
    "            i += 1\n",
    "            cur += i\n",
    "        cur = 1\n",
    "        while n > cur:\n",
    "            n -= cur\n",
    "            j += 1\n",
    "            cur += 1\n",
    "        return (i - 1) * i // 2 + j"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def get_ans(self, n: int) -> int:\n",
    "        delat = (1 + 8 * n)**(1/2)\n",
    "        res = (delat - 1)/2\n",
    "        return math.ceil(res)\n",
    "\n",
    "    def minimumBoxes(self, n: int) -> int:\n",
    "        # 潜在的x\n",
    "        x = int((6 * n) ** (1 / 3))\n",
    "        # 此时接触地面的数量\n",
    "        ans = x * (x + 1) // 2\n",
    "        # 总方块的数量\n",
    "        max_n = x * (x + 1) * (x + 2) // 6\n",
    "        # 超了， 没有叠满\n",
    "        if max_n > n:\n",
    "            # 把最后一层在总方块数中删除\n",
    "            max_n -= ans\n",
    "            # 答案删除满叠的外层\n",
    "            ans -= x\n",
    "        # 计算叠了多少个j\n",
    "        j = math.ceil(self.get_ans(n - max_n))\n",
    "        return ans+j\n",
    "\n",
    "    def minimumBoxes3(self, n: int) -> int:\n",
    "        curr = 0\n",
    "        i = j = 0\n",
    "        while curr < n:\n",
    "            j += 1\n",
    "            i += j\n",
    "            curr += i\n",
    "        if curr == n:\n",
    "            return i\n",
    "        curr -= i\n",
    "        i -= j\n",
    "        j = math.ceil(self.get_ans(n - curr))\n",
    "        return i+j\n",
    "\n",
    "    def minimumBoxes2(self, n: int) -> int:\n",
    "        curr = 0\n",
    "        i = j = 0\n",
    "        while curr < n:\n",
    "            j += 1\n",
    "            i += j\n",
    "            curr += i\n",
    "        if curr == n:\n",
    "            return i\n",
    "        curr -= i\n",
    "        i -= j\n",
    "        j = 0\n",
    "        while curr < n:\n",
    "            j += 1\n",
    "            curr += j\n",
    "        return i+j\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumBoxes(self, n: int) -> int:\n",
    "        for i in range(n):\n",
    "            if i*(i+1)*(i+2)//6 == n:\n",
    "                return i*(i+1)//2\n",
    "            if i*(i+1)*(i+2)//6 > n:\n",
    "                i -= 1\n",
    "                break\n",
    "        remain = n-i*(i+1)*(i+2)//6\n",
    "        botton = i*(i+1)//2\n",
    "        for j in range(i+2):\n",
    "            k = j*(j+1)//2\n",
    "            if remain <= k:\n",
    "                return botton+j"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def func1(n):\n",
    "    return (n ** 3 + 3 * n * n + 2 * n) // 6\n",
    "\n",
    "\n",
    "def func2(n):\n",
    "    return (n * n + n) // 2\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minimumBoxes(self, n: int) -> int:\n",
    "        if n == 1:\n",
    "            return 1\n",
    "        if n == 2:\n",
    "            return 2\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        for i in range(1,n):\n",
    "            if func1(i) == n:\n",
    "                return func2(i)\n",
    "            if func1(i) > n:\n",
    "                tmp = i - 1\n",
    "                break\n",
    "        step = i - 1\n",
    "        ans = func1(step)\n",
    "\n",
    "        for j in range(1, n):\n",
    "            ans += j\n",
    "            if ans >= n:\n",
    "                return func2(step) + j\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumBoxes(self, n: int) -> int:\n",
    "        if n <= 2:\n",
    "            return n\n",
    "        for i in range(1, n):\n",
    "            num = i * (i + 1) * (i + 2) // 6\n",
    "            if num == n:\n",
    "                return i * (i + 1) // 2\n",
    "            if num > n:\n",
    "                i -= 1\n",
    "                break\n",
    "\n",
    "        num = i * (i + 1) * (i + 2) // 6\n",
    "        for j in range(1, n):\n",
    "            num += j\n",
    "            if num >= n:\n",
    "                return j + i * (i + 1) // 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumBoxes(self, n: int) -> int:\n",
    "        \n",
    "        \n",
    "        now=0\n",
    "        nextcengcount=1\n",
    "        nowceng=0\n",
    "        while now+nextcengcount<=n:\n",
    "            now+=nextcengcount\n",
    "            nowceng+=1\n",
    "            nextcengcount=(nowceng+2)*(nowceng+1)//2\n",
    "            \n",
    "        # left=n-now\n",
    "        ans=(nowceng+1)*nowceng//2\n",
    "        # print(ans)\n",
    "        # print(now)\n",
    "        \n",
    "        temp=1\n",
    "        while now<n:\n",
    "            ans+=1\n",
    "            now+=temp\n",
    "            temp+=1\n",
    "        \n",
    "        \n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumBoxes(self, n: int) -> int:\n",
    "        ans = max_n = 0\n",
    "        i = j = 1\n",
    "        while max_n + ans + i <= n:\n",
    "            ans += i\n",
    "            max_n += ans\n",
    "            i += 1\n",
    "        while max_n < n:\n",
    "            ans += 1\n",
    "            max_n += j\n",
    "            j += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumBoxes(self, n: int) -> int:\n",
    "        ans = max_n = 0\n",
    "        i = j = 1\n",
    "        while max_n + ans + i <= n:\n",
    "            ans += i\n",
    "            max_n += ans\n",
    "            i += 1\n",
    "        while max_n < n:\n",
    "            ans += 1\n",
    "            max_n += j\n",
    "            j += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def func1(n):\n",
    "    return (n ** 3 + 3 * n * n + 2 * n) // 6\n",
    "\n",
    "\n",
    "def func2(n):\n",
    "    return (n * n + n) // 2\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minimumBoxes(self, n: int) -> int:\n",
    "        if n == 1:\n",
    "            return 1\n",
    "        if n == 2:\n",
    "            return 2\n",
    "        i = 0\n",
    "\t\t\n",
    "        while True:\n",
    "            i += 1\n",
    "            if func1(i) == n:\n",
    "                return func2(i)\n",
    "            if func1(i) > n:\n",
    "                i -= 1\n",
    "                break\n",
    "        ans = func1(i)\n",
    "                \n",
    "        for j in range(1,n):\n",
    "            ans += j\n",
    "            if ans >= n:\n",
    "                return func2(i) + j"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumBoxes(self, n: int) -> int:\n",
    "        i=0\n",
    "        while (i*(i+1)*(i+2))/6<n:\n",
    "            i+=1\n",
    "        i-=1\n",
    "        res=((1+i)*i)/2\n",
    "        \n",
    "        tmp=n-(i*(i+1)*(i+2))/6\n",
    "        k=0\n",
    "        while ((k+1)*k)/2<tmp:\n",
    "            k+=1\n",
    "            \n",
    "        return int(res+k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumBoxes(self, n: int) -> int:\n",
    "        curNum, totalNum, lNum = 1, 1, 1\n",
    "        while totalNum < n:\n",
    "            lNum += 1\n",
    "            curNum += lNum\n",
    "            totalNum += curNum\n",
    "        leftNum = n - (totalNum - curNum)\n",
    "        curNum, totalNum = 1, 1\n",
    "        while totalNum < leftNum:\n",
    "            curNum += 1\n",
    "            totalNum += curNum\n",
    "        ret = (lNum -1) * lNum // 2 + curNum\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumBoxes(self, n: int) -> int:\n",
    "        cur = i = j = 1\n",
    "        while n > cur:\n",
    "            n -= cur\n",
    "            i += 1\n",
    "            cur += i\n",
    "        cur = 1\n",
    "        while n > cur:\n",
    "            n -= cur\n",
    "            j += 1\n",
    "            cur += 1\n",
    "        return (i - 1) * i // 2 + j"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumBoxes(self, n: int) -> int:\n",
    "        ans = max_n = 0\n",
    "        i = j = 1\n",
    "        while max_n + ans + i <= n:\n",
    "            ans += i\n",
    "            max_n += ans\n",
    "            i += 1\n",
    "        while max_n < n:\n",
    "            ans += 1\n",
    "            max_n += j\n",
    "            j += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumBoxes(self, n: int) -> int:\n",
    "        def f(x):\n",
    "            left, right = 1, x\n",
    "            while left <= right:\n",
    "                mid = (left + right) >> 1\n",
    "                if mid * (1 + mid) / 2 < x:\n",
    "                    left = mid + 1\n",
    "                else:\n",
    "                    right = mid - 1\n",
    "            return left\n",
    "        \n",
    "        def s(x):\n",
    "            ans = x\n",
    "            u = x - f(x)\n",
    "            while u > 0:\n",
    "                ans += u\n",
    "                u = u - f(u)\n",
    "            return ans\n",
    "\n",
    "        left, right = 1, n\n",
    "        while left <= right:\n",
    "            mid = (left + right) >> 1\n",
    "            if s(mid) < n:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "\n",
    "        return left\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minimumBoxes(self, n: int) -> int:\n",
    "        curr = 0\n",
    "        i = j = 0\n",
    "        while curr < n:\n",
    "            j += 1\n",
    "            i += j\n",
    "            curr += i\n",
    "        if curr == n:\n",
    "            return i\n",
    "        curr -= i\n",
    "        i -= j\n",
    "        j_n = n - curr\n",
    "        delat = (1 + 8 * j_n)**(1/2)\n",
    "        j = math.ceil((delat - 1)/2)\n",
    "        return i+j\n",
    "\n",
    "    def minimumBoxes2(self, n: int) -> int:\n",
    "        curr = 0\n",
    "        i = j = 0\n",
    "        while curr < n:\n",
    "            j += 1\n",
    "            i += j\n",
    "            curr += i\n",
    "        if curr == n:\n",
    "            return i\n",
    "        curr -= i\n",
    "        i -= j\n",
    "        j = 0\n",
    "        while curr < n:\n",
    "            j += 1\n",
    "            curr += j\n",
    "        return i+j\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumBoxes(self, n: int) -> int:\n",
    "        all_l = 0\n",
    "        down_l = []\n",
    "        for i in range(1, n+1):\n",
    "            for j in range(1, i+1):\n",
    "                all_l += j\n",
    "                if all_l >= n:\n",
    "                    return sum(down_l)+j\n",
    "            down_l.append(i)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumBoxes(self, n: int) -> int:\n",
    "        ans = max_n = 0\n",
    "        i = j = 1\n",
    "        while max_n + ans + i <= n:\n",
    "            ans += i\n",
    "            max_n += ans\n",
    "            i += 1\n",
    "        while max_n < n:\n",
    "            ans += 1\n",
    "            max_n += j\n",
    "            j += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumBoxes(self, n: int) -> int:\n",
    "        x = int((6 * n) ** (1 / 3))\n",
    "        ans = x * (x + 1) // 2\n",
    "        max_n = x * (x + 1) * (x + 2) // 6\n",
    "        if max_n > n:\n",
    "            max_n -= ans\n",
    "            ans -= x\n",
    "        return ans + ceil((-1 + (1 + 8 * (n - max_n)) ** 0.5) / 2)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def get_ans(self, n: int) -> int:\n",
    "        delat = (1 + 8 * n)**(1/2)\n",
    "        res = (delat - 1)/2\n",
    "        return res\n",
    "\n",
    "    def minimumBoxes(self, n: int) -> int:\n",
    "        curr = 0\n",
    "        i = j = 0\n",
    "        while curr < n:\n",
    "            j += 1\n",
    "            i += j\n",
    "            curr += i\n",
    "        if curr == n:\n",
    "            return i\n",
    "        curr -= i\n",
    "        i -= j\n",
    "        j = math.ceil(self.get_ans(n - curr))\n",
    "        return i+j\n",
    "\n",
    "    def minimumBoxes2(self, n: int) -> int:\n",
    "        curr = 0\n",
    "        i = j = 0\n",
    "        while curr < n:\n",
    "            j += 1\n",
    "            i += j\n",
    "            curr += i\n",
    "        if curr == n:\n",
    "            return i\n",
    "        curr -= i\n",
    "        i -= j\n",
    "        j = 0\n",
    "        while curr < n:\n",
    "            j += 1\n",
    "            curr += j\n",
    "        return i+j\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumBoxes(self, n: int) -> int:\n",
    "        left, right = 0, n\n",
    "        while left < right:\n",
    "            mid = (left + right+1) // 2\n",
    "            if mid*(mid+1)*(mid+2) // 6 <= n:\n",
    "                left = mid\n",
    "            else:\n",
    "                right = mid-1\n",
    "        basic = left * (left+1) // 2\n",
    "        diff = n - left*(left+1)*(left+2) // 6\n",
    "        left, right = 0, left+1\n",
    "        while left < right:\n",
    "            mid = (left + right) // 2\n",
    "            if mid*(mid+1) // 2 >= diff:\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid+1\n",
    "        return basic + left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumBoxes(self, n: int) -> int:\n",
    "        cur = i = j = 1\n",
    "        while n > cur:\n",
    "            n -= cur\n",
    "            i += 1\n",
    "            cur += i\n",
    "        cur = 1\n",
    "        while n > cur:\n",
    "            n -= cur\n",
    "            j += 1\n",
    "            cur += 1\n",
    "        return (i - 1) * i // 2 + j\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumBoxes(self, n: int) -> int:\n",
    "        if n<=2:\n",
    "            return n\n",
    "        for i in range(1, n):\n",
    "            sum1 = i * (i + 1) * (i + 2)  // 6\n",
    "            if sum1 == n:\n",
    "                return i * (i + 1) // 2\n",
    "            if sum1 > n:\n",
    "                i -= 1\n",
    "                break\n",
    "        num = i * (i + 1)*(i + 2) // 6\n",
    "        step = i\n",
    "        for j in range(1, n):\n",
    "            num += j\n",
    "            if num >= n:\n",
    "                return step * (step + 1) //2 +j\n",
    "        assert False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumBoxes(self, n: int) -> int:\n",
    "        k = 0\n",
    "        while n > k * (k + 1) * (k + 2) // 6:\n",
    "            k += 1\n",
    "\n",
    "        # 找到了最大的完整的金字塔层数 k-1\n",
    "        # k-1 层的立方体数量是 k*(k-1)/2\n",
    "        total = (k - 1) * k // 2\n",
    "        n -= (k - 1) * k * (k + 1) // 6\n",
    "\n",
    "        # 为剩余的立方体找位置\n",
    "        base = 1\n",
    "        while n > 0:\n",
    "            total += 1\n",
    "            n -= base\n",
    "            base += 1\n",
    "\n",
    "        return total\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def func1(n):\n",
    "    return (n ** 3 + 3 * n * n + 2 * n) // 6\n",
    "\n",
    "\n",
    "def func2(n):\n",
    "    return (n * n + n) // 2\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minimumBoxes(self, n: int) -> int:\n",
    "        if n == 1:\n",
    "            return 1\n",
    "        if n == 2:\n",
    "            return 2\n",
    "\n",
    "        for i in range(1,n):\n",
    "            if func1(i) == n:\n",
    "                return func2(i)\n",
    "            if func1(i) > n:\n",
    "                #tmp = i - 1\n",
    "                break\n",
    "        step = i - 1\n",
    "        ans = func1(step)\n",
    "\n",
    "        for j in range(1, n):\n",
    "            ans += j\n",
    "            if ans >= n:\n",
    "                return func2(step) + j\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumBoxes(self, n: int) -> int:\n",
    "        h = 0\n",
    "        while h * (h + 1) * (h + 2) // 6 <= n:\n",
    "            h += 1 \n",
    "        h -= 1 \n",
    "        res = h * (h + 1) // 2 \n",
    "        base = 0\n",
    "        remain = n - h * (h + 1) * (h + 2) // 6 \n",
    "        while remain > 0:\n",
    "            base += 1 \n",
    "            res += 1 \n",
    "            remain -= base\n",
    "        return res \n",
    "\n",
    "        h = 0\n",
    "        while h * (h + 1) * (h + 2) // 6 <= n:\n",
    "            h += 1 \n",
    "        h -= 1 \n",
    "        res = h * (h + 1) // 2 \n",
    "        base = 0\n",
    "        remain = n - h * (h + 1) * (h + 2) // 6 \n",
    "        while remain > 0:\n",
    "            remain -= base\n",
    "            base += 1 \n",
    "            res += 1 \n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumBoxes(self, n: int) -> int:\n",
    "        for i in range(1, n + 1):\n",
    "            sum0 = i * (i + 1) * (i + 2) // 6\n",
    "            if sum0 > n:\n",
    "                n0 = i - 1\n",
    "                sum0 = (i-1) * (i + 1) * i // 6\n",
    "                break\n",
    "            if sum0 == n:\n",
    "                return i*(i+1)//2\n",
    "    \n",
    "    \n",
    "        bottom = n0 * (n0 + 1) // 2\n",
    "        for i in range(1, n0 + 2):\n",
    "            if n - sum0 <= i * (i + 1) // 2:\n",
    "                return bottom + i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumBoxes(self, n: int) -> int:\n",
    "        for i in range(n):\n",
    "            if i*(i+1)*(i+2)//6 == n:\n",
    "                return i*(i+1)//2\n",
    "            if i*(i+1)*(i+2)//6 > n:\n",
    "                i -= 1\n",
    "                break\n",
    "        remain = n-i*(i+1)*(i+2)//6\n",
    "        botton = i*(i+1)//2\n",
    "        for j in range(i+2):\n",
    "            k = j*(j+1)//2\n",
    "            if remain <= k:\n",
    "                return botton+j"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumBoxes(self, n: int) -> int:\n",
    "        if n == 1:\n",
    "            return 1\n",
    "        if n == 2:\n",
    "            return 2    \n",
    "        for i in range(1, n):\n",
    "            num = i*(i+1)*(i+2)//6\n",
    "            if num == n:\n",
    "                return (1+i)*i//2\n",
    "            if num > n:\n",
    "                tmp = i-1\n",
    "                break    \n",
    "        step = i-1\n",
    "        num = step*(step+1)*(step+2)//6\n",
    "        \n",
    "        for j in range(1, n):\n",
    "            num += j\n",
    "            if num >= n:\n",
    "                return step*(step+1)//2 + j  \n",
    "        assert False\t\t"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumBoxes(self, n: int) -> int:\n",
    "        for i in range(1, n+1):\n",
    "            if i * (i + 1) * (i + 2) / 6 > n:\n",
    "                break\n",
    "            else:\n",
    "                n0 = i\n",
    "        bottom = n0 * (n0 + 1) // 2\n",
    "        sum0 = n0 * (n0 + 1) * (n0 + 2) // 6\n",
    "        print(n0)\n",
    "        if n - sum0 == 0:\n",
    "            return bottom\n",
    "        # print(n - sum0)\n",
    "        for i in range(1, n0+2):\n",
    "            if n - sum0 <= i*(i+1)//2:\n",
    "                return bottom + i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumBoxes(self, n: int) -> int:\n",
    "        curr = 0\n",
    "        i = j = 0\n",
    "        while curr < n:\n",
    "            j += 1\n",
    "            i += j\n",
    "            curr += i\n",
    "        if curr == n:\n",
    "            return i\n",
    "        curr -= i\n",
    "        i -= j\n",
    "        j = 0\n",
    "        while curr < n:\n",
    "            j += 1\n",
    "            curr += j\n",
    "        return i+j"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumBoxes(self, n: int) -> int:\n",
    "        h = 0\n",
    "        while h * (h + 1) * (h + 2) // 6 <= n:\n",
    "            h += 1 \n",
    "        h -= 1 \n",
    "        res = h * (h + 1) // 2 \n",
    "        base = 0\n",
    "        remain = n - h * (h + 1) * (h + 2) // 6 \n",
    "        while remain > 0:\n",
    "            base += 1 \n",
    "            res += 1 \n",
    "            remain -= base\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumBoxes(self, n: int) -> int:\n",
    "        box = 1\n",
    "        incre = 2\n",
    "        sum_box = 0\n",
    "        boxes = []\n",
    "        while sum_box + box <= n:\n",
    "            boxes.append(box)\n",
    "            sum_box += box\n",
    "            box += incre\n",
    "            incre += 1\n",
    " \n",
    "        \n",
    "        ab_box = n - sum_box\n",
    "        num = 1\n",
    "        while ab_box>0:\n",
    "            boxes[-1] += 1\n",
    "            ab_box-=num\n",
    "            num += 1\n",
    "        return boxes[-1]\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumBoxes(self, n: int) -> int:\n",
    "        # 每层方盒个数为 1 3  6 10 15, 差值递增 2 3 4 5 ...\n",
    "        # 分别对应 n =   1 4 10 20 35\n",
    "        # 从上往下第 m 层方盒数量是  (m^2 + m) / 2\n",
    "        \n",
    "        total = 0  # 计算前m层的盒子总数\n",
    "        m = 0\n",
    "        last = 0\n",
    "        while True:\n",
    "            m += 1\n",
    "            cur = (m ** 2 + m) // 2\n",
    "            last_total = total\n",
    "            total += cur\n",
    "            if total == n:\n",
    "                return cur\n",
    "            if total > n:\n",
    "                # 无法满足标准的 m 层\n",
    "                diff = n - last_total  # 多余了 diff\n",
    "                # 下层 + 2盒子, 上一层就可多放 1 个盒子， 满足 1 + 2 + 3\n",
    "                k = 0  # 多余的diff可在最低层放置k个盒子\n",
    "                add = 0\n",
    "                while True:\n",
    "                    k += 1\n",
    "                    add += k\n",
    "                    if add >= diff:\n",
    "                        break\n",
    "                return last + k\n",
    "            last = cur\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumBoxes(self, n: int) -> int:\n",
    "        i = bisect_left(range(n+1),n,key=lambda i:i*(i+1)*(i+2)//6)\n",
    "        n -= (i-1)*i*(i+1)//6\n",
    "        j = bisect_left(range(n+1),n,key=lambda j:j*(j+1)//2)\n",
    "        return (i-1)*i//2+j\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumBoxes(self, n: int) -> int:\n",
    "        data = [i * (i + 1) // 2 for i in range(isqrt(2 * n) + 1)]\n",
    "\n",
    "        l, r = 1, n\n",
    "        while l < r:\n",
    "            m = (l + r) >> 1\n",
    "            \n",
    "            cnt = x = m\n",
    "            while cnt < n:\n",
    "                i = bisect_right(data, x) - 1\n",
    "                if i == 0:\n",
    "                    break\n",
    "\n",
    "                t = data[i - 1]\n",
    "                if x != data[i]:\n",
    "                    t += x - data[i] - 1\n",
    "                \n",
    "                cnt += t\n",
    "                x = t\n",
    "            \n",
    "            if cnt >= n:\n",
    "                r = m\n",
    "            else:\n",
    "                l = m + 1\n",
    "        \n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumBoxes(self, n: int) -> int:\n",
    "        d = [0]\n",
    "        s = 0\n",
    "        t = 1\n",
    "        while s <= n:\n",
    "            s = s + t\n",
    "            t += 1\n",
    "            d.append(s)\n",
    "        s = 0\n",
    "        t = 1\n",
    "        while s <= n:\n",
    "            res = n - s\n",
    "            ans = d[t-1]\n",
    "            s = s + d[t]\n",
    "            t += 1\n",
    "        p = bisect.bisect_left(d, res)\n",
    "        ans += p\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumBoxes(self, n: int) -> int:\n",
    "        @cache\n",
    "        def f(x):\n",
    "            left, right = 1, x\n",
    "            while left <= right:\n",
    "                mid = (left + right) >> 1\n",
    "                if mid * (1 + mid) / 2 < x:\n",
    "                    left = mid + 1\n",
    "                else:\n",
    "                    right = mid - 1\n",
    "            return left\n",
    "        \n",
    "        def s(x):\n",
    "            ans = x\n",
    "            u = x - f(x)\n",
    "            while u > 0:\n",
    "                ans += u\n",
    "                u = u - f(u)\n",
    "            return ans\n",
    "\n",
    "        left, right = 1, n\n",
    "        while left <= right:\n",
    "            mid = (left + right) >> 1\n",
    "            if s(mid) < n:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "\n",
    "        return left\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
